#include <bits/stdc++.h>
#define ll long long
using namespace std;


struct control {
    int ct, val;
    control(int Ct, int Val = -1)
        : ct(Ct)
        , val(Val)
    {
    }
    inline control operator()(int Val)
    {
        return control(ct, Val);
    }
} _endl(0), _prs(1), _setprecision(2);
struct FastIO {
#define IOSIZE 1000000
    char in[IOSIZE], *p, *pp, out[IOSIZE], *q, *qq, ch[20], *t, b, K, prs;
    FastIO()
        : p(in)
        , pp(in)
        , q(out)
        , qq(out + IOSIZE)
        , t(ch)
        , b(1)
        , K(6)
    {
    }
    ~FastIO()
    {
        flush();
    }
    void flush()
    {
        fwrite(out, 1, q - out, stdout);
        q = out;
    }
    inline char getch()
    {
        return p == pp && (pp = (p = in) + fread(in, 1, IOSIZE, stdin), p == pp) ? b = 0, EOF : *p++;
    }
    inline void putch(char x)
    {
        q == qq && (fwrite(out, 1, q - out, stdout), q = out), *q++ = x;
    }
    inline void puts(const char str[])
    {
        fwrite(out, 1, q - out, stdout), fwrite(str, 1, strlen(str), stdout), q = out;
    }
    inline void getline(std::string& s)
    {
        s = "";
        for (char ch; (ch = getch()) != '\n' && b;)
            s += ch;
    }
#define indef(T)                                               \
    inline FastIO& operator>>(T& x)                            \
    {                                                          \
        x = 0;                                                 \
        char f = 0, ch;                                        \
        while (!isdigit(ch = getch()) && b)                    \
            f |= ch == '-';                                    \
        while (isdigit(ch))                                    \
            x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch(); \
        return x = f ? -x : x, *this;                          \
    }
    indef(int) indef(long long) inline FastIO& operator>>(char& ch)
    {
        return ch = getch(), *this;
    }
    inline FastIO& operator>>(std::string& s)
    {
        s = "";
        char ch;
        while (isspace(ch = getch()) && b)
            ;
        while (!isspace(ch) && b)
            s += ch, ch = getch();
        return *this;
    }
    inline FastIO& operator>>(double& x)
    {
        x = 0;
        char f = 0, ch;
        double d = 0.1;
        while (!isdigit(ch = getch()) && b)
            f |= (ch == '-');
        while (isdigit(ch))
            x = x * 10 + (ch ^ 48), ch = getch();
        if (ch == '.')
            while (isdigit(ch = getch()))
                x += d * (ch ^ 48), d *= 0.1;
        return x = f ? -x : x, *this;
    }
#define outdef(_T)                                            \
    inline FastIO& operator<<(_T x)                           \
    {                                                         \
        !x && (putch('0'), 0), x < 0 && (putch('-'), x = -x); \
        while (x)                                             \
            *t++ = x % 10 + 48, x /= 10;                      \
        while (t != ch)                                       \
            putch(*--t);                                      \
        return *this;                                         \
    }
    outdef(int) outdef(long long) inline FastIO& operator<<(char ch)
    {
        return putch(ch), *this;
    }
    inline FastIO& operator<<(const char str[])
    {
        return puts(str), *this;
    }
    inline FastIO& operator<<(const std::string& s)
    {
        return puts(s.c_str()), *this;
    }
    inline FastIO& operator<<(double x)
    {
        int k = 0;
        this->operator<<(int(x));
        putch('.');
        x -= int(x);
        prs && (x += 5 * pow(10, -K - 1));
        while (k < K)
            putch(int(x *= 10) ^ 48), x -= int(x), ++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl)
    {
        switch (cl.ct) {
        case 0:
            putch('\n');
            break;
        case 1:
            prs = cl.val;
            break;
        case 2:
            K = cl.val;
            break;
        }
        return *this;
    }
    inline operator bool()
    {
        return b;
    }
} io;

bool st;
const int Maxn=5e5+7;
const int inf=1e9;
int n,m,Q;
vector<int>e[Maxn];
int col[Maxn],cnt,vis[Maxn];

void dfs(int u){
	col[u]=cnt;
	for(auto v:e[u]) if(!col[v]) dfs(v);
}

vector<pair<int,int> >q[Maxn];
int ans[Maxn],lst[Maxn],ps[Maxn];

class BIT{
	#define lowbit(x) (x&-x)
	public:
		inline void init(int l){sz=l;
		for(int i=0;i<=sz;i++)tr[i]=inf;}
		inline void add(int x,int k){
			while(x) tr[x]=min(tr[x],k),x-=lowbit(x);
		}
		inline int query(int x){
			int s=inf;
			while(x<=sz) s=min(s,tr[x]),x+=lowbit(x);
			return s;  
		}
	private:
		int tr[Maxn],sz;
}t[6];

int main(){
    freopen("destory.in","r",stdin);
    freopen("destory.out","w",stdout);
   
   	io>>n>>m>>Q;
   	for(int i=1;i<=m;i++){
		int u,v;
		io>>u>>v;
		e[u].emplace_back(v);
		e[v].emplace_back(u); 
   	}
   	for(int i=1;i<=n;i++){
   		if(!col[i]){
   			++cnt;
   			dfs(i);
		   }	
	}
   
   	if(1ll*n*Q<=5e7){
		while(Q--){
			int l,r;
			io>>l>>r;
			int nowr=l-1,c=0,rc=0;
			for(int i=l;i<=r;i++) if(!vis[col[i]]) ++c,vis[col[i]]=1;
			for(int i=l;i<=r;i++) vis[col[i]]=0;
			int ans=inf;
			for(int i=l;i<=r;i++){
				while(rc<c and nowr<r){
					nowr++;
					if(!vis[col[nowr]]){
						rc++;
					}
					vis[col[nowr]]++;
				}
				if(rc==c) ans=min(ans,nowr-i+1);
				vis[col[i]]--;
				if(!vis[col[i]]) rc--;
			}
			io<<ans<<"\n"; 
			for(int i=l;i<=r;i++) vis[col[i]]=0;
		}
	}
	else{
		for(int i=1;i<=5;i++) t[i].init(n+5);
		for(int i=1;i<=Q;i++){
			int l,r;
			io>>l>>r;
			q[r].emplace_back(l,i);
		}
		for(int i=1;i<=n;i++){
			int p=lst[col[i]];
			for(int j=p+1;j<=i;j++){
				ps[j]++;
				t[ps[j]].add(j,i-j+1);
			}
			lst[col[i]]=i;
			for(auto iq:q[i]){
				int l=iq.first,id=iq.second;
				ans[id]=t[ps[l]].query(l);
			}
		}
		for(int i=1;i<=Q;i++) io<<ans[i]<<"\n";
	}
   
    io.flush();
    return 0;
}
/*
5 2 5
2 2
4 1
1 1
1 1
2 5
4 5
3 5
*/
